<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>2277：[Poi2011]Strongbox</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2011]Strongbox</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2011]Strongbox</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Poi2011]Strongbox                </h1>
                <p>时间限制：60s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：32MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="line-height: 140%" align="left"><span style="font-size: 10pt; color: #444444; line-height: 140%">Byteasar is a famous safe-cracker, who renounced his criminal activity and got into testing and certifying anti-burglary devices. He has just received a new kind of strongbox for tests: a combinatorial safe. A combinatorial safe is something different from a combination safe, even though it is opened with a rotary dial. The dial can be set in different positions, numbered from 0 to n-1. Setting the dial in some of these positions opens the safe, while in others it does not. And here is the combinatorial property, from which the name comes from: if x and y are opening positions, then so is (x+y) mod n too; note that is holds for x=y as well. </span></div>
<div style="line-height: 140%" align="left"><span style="font-size: 10pt; color: #444444; line-height: 140%">Byteasar tried k different positions of the dial: m1,m2&hellip;.mk. The positions M1,M 2&hellip;.Mk-1 did not open the safe, only the last position Mk did. Byteasar is already tired from checking these K positions and has thus absolutely no intention of trying the remaining ones. He would like to know however, based on what he already knows about the positions he tried, what is the maximum possible number of positions that open the safe. Help him by writing an appropriate program! </span></div>
<p>有一个密码箱，0到n-1中的某些整数是它的密码。<br />
且满足，如果a和b都是它的密码，那么(a+b)%n也是它的密码(a,b可以相等)<br />
某人试了k次密码，前k-1次都失败了，最后一次成功了。<br />
问：该密码箱最多有多少不同的密码。</p>
<p></p></p><hr/><h3>输入格式</h3><p><div style="line-height: 140%" align="left"><span style="font-size: 10pt; color: #444444; line-height: 140%">The first line of the standard input gives two integers N and k, separated by a single space, (1&lt;=K&lt;=250000,k&lt;=N&lt;=10^14), The second line holds K different integers, also separated by single spaces, m1,m2&hellip;.mk, 0&lt;=Mi&lt;N. You can assume that the input data correspond to a certain combinatorial safe that complies with the description above. </span></div>
<div style="line-height: 140%" align="left"><span style="font-size: 10pt; color: #444444; line-height: 140%">In tests worth approximately 70% of the points it holds that k&lt;=1000. In some of those tests, worth approximately 20% of the points, the following conditions hold in addition: N&lt; 10 ^8 and K&lt;=100. </span></div>
<p>第一行n，k<br />
下面一行k个整数，表示每次试的密码<br />
保证存在合法解</p>
<p>1&lt;=k&lt;=250000 k&lt;=n&lt;=10^14</p>
<p></p></p><hr/><h3>输出格式</h3><p><div style="line-height: 140%" align="left"><span style="font-size: 10pt; color: #444444; line-height: 140%">Your program should print out to the first and only line of the standard output a single integer: the maximum number of the dial's positions that can open the safe. </span></div>
<p>一行，表示结果</p>
<p></p></p><hr/><h3>样例输入</h3><pre>42 5
28 31 10 38 24
</pre><hr/><h3>样例输出</h3><pre>14</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=2277" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=2277" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>